//
// Created by Administrator on 2021/5/19.
//
#include <vector>
#include <iostream>
#include <queue>
#include <algorithm>

using namespace std;

class Solution {
public:
    vector<vector<int>> kClosest(vector<vector<int>> &points, int k) { // 排序
        sort(points.begin(), points.end(), [](vector<int> &a, vector<int> &b) {
            return a[0] * a[0] + a[1] * a[1] < b[0] * b[0] + b[1] * b[1];
        });

        return {points.begin(), points.begin() + k};
    }
};

class Solution2 { // 题解 堆
public:
    vector<vector<int>> kClosest(vector<vector<int>> &points, int K) {
        priority_queue<pair<int, int>> q;
        for (int i = 0; i < K; ++i) {
            q.emplace(points[i][0] * points[i][0] + points[i][1] * points[i][1], i);
        }
        int n = (int) points.size();
        for (int i = K; i < n; ++i) {
            int dist = points[i][0] * points[i][0] + points[i][1] * points[i][1];
            if (dist < q.top().first) {
                q.pop();
                q.emplace(dist, i);
            }
        }
        vector<vector<int>> ans;
        while (!q.empty()) {
            ans.push_back(points[q.top().second]);
            q.pop();
        }
        return ans;
    }
};


int main() {
    vector<vector<int>> points{{1,  3},
                               {-2, 2},
                               {3,  3}};
    Solution2 sol;
    auto ans = sol.kClosest(points, 1);
    for (auto &x:ans) {
        cout << x[0] << " " << x[1] << endl;
    }
    return 0;
}